home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2237 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.3 KB
  1. Path: amaryllisp1.appsig.com!user
  2. From: larry_kearney@appsig.com (Lawrence Kearney)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: Fri, 19 Jan 1996 13:35:26 -0700
  6. Organization: Applied Signal Technology
  7. Message-ID: <larry_kearney-1901961335260001@amaryllisp1.appsig.com>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>
  9. NNTP-Posting-Host: amaryllisp1.appsig.com
  10.  
  11. > Is there a fast way to decide whether a number n is a power of 2?
  12. >...
  13. > Since I am dealing with unsigned long ints, I guess I can just store all
  14. > 31 powers of 2 in a table and compare to n.  Though I don't know a fast
  15. > algorithm to compare a number to 31 numbers in an array.
  16. > Thanks very much for any help.
  17. > 
  18. > Bill Simpson
  19.  
  20. I think that if you use a table lookup using a binary search algorithm,the
  21. maximum number of comparisons that you would have to make would be either
  22. 5 or 6 as a worst case. This would have to be considerably faster that
  23. performing a floating point log and divide.
  24.  
  25. To eliminate odd numbers, you might first want to test to see if the
  26. number is odd or even by looking at the LSB. If the bit is 0, then procede
  27. to the table lookup. If the bit is set, it obviously can't be an even
  28. power of two.
  29.  
  30. -- 
  31. Larry Kearney                   |   "You want fries with that?"
  32. Applied Signal Technology       |
  33. larry_kearney@appsig.com        |
  34.